package main

import (
	"fmt"
)

/**
执行用时：100 ms, 在所有 Go 提交中击败了17.23%的用户
内存消耗：9.3 MB, 在所有 Go 提交中击败了24.96%的用户
 */
func maxSubArray(nums []int) int {

	f, res := nums[0], nums[0]
	for i := 1; i < len(nums); i++ {
		f = max(f, 0) + nums[i]
		res = max(res, f)
	}
	return res
}

func max(a int, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func main() {

	nums := []int{2, -1, -3, 4, -1, 2, 1, -5, 4}
	fmt.Println(maxSubArray(nums))
}
